package com.taldh.algorithm.array;

import org.junit.Assert;
import org.junit.Test;

public class FindMedianSortedArraysSolution {
    /**
     * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
     *
     * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     *
     * 你可以假设 nums1 和 nums2 不会同时为空。
     *
     * 示例 1:
     *
     * nums1 = [1, 3]
     * nums2 = [2]
     *
     * 则中位数是 2.0
     * 示例 2:
     *
     * nums1 = [1, 2]
     * nums2 = [3, 4]
     *
     * 则中位数是 (2 + 3)/2 = 2.5
     *
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        // m+n的算法
        if (nums1 == null) {
            nums1 = new int[]{};
        }
        if (nums2 == null) {
            nums2 = new int[]{};
        }
//        int[] nums = new int[nums1.length + nums2.length];
//
//        for (int i = 0, j = 0, z = 0; z < nums.length ; z ++) {
//            if (j >= nums2.length || (i < nums1.length && nums1[i] < nums2[j])) {
//                nums[z] = nums1[i];
//                i ++;
//            } else if (i >= nums1.length || nums1[i] >= nums2[j]){
//                nums[z] = nums2[j];
//                j ++;
//            }
//        }
//
//        int media = nums.length / 2;
//        if (nums.length % 2 == 0) {
//            return (nums[media-1] + nums[media]) / 2.0;
//        } else {
//            return nums[media];
//        }
        //从小达到遍历法
//        int m = nums1.length;
//        int n = nums2.length;
//        int left = -1, right = -1;
//        int half = (m + n) / 2;
//        int aStart = 0, bStart = 0;
//        for (int i = 0; i < half + 1 ; i++) {
//            left = right;
//            if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
//                right = nums1[aStart++];
//            } else {
//                right = nums2[bStart++];
//            }
//        }
//        if ((m+n) % 2 == 0) {
//            return (left + right) / 2.0;
//        } else {
//            return right;
//        }
        //二分查找法,查找第k个小的数。k=(m+n)/2
        int m = nums1.length;
        int n = nums2.length;
        int half = (m + n) / 2;
        if ((m+n) % 2 == 0) {
            return (getMinKth(nums1, nums2, 0, m, 0,n, half) +
                    getMinKth(nums1, nums2, 0, m, 0,n, half + 1)) / 2.0;
        } else {
            return getMinKth(nums1, nums2, 0, m, 0,n, half+1);
        }
    }

    private double getMinKth(int[] nums1, int[] nums2, int startPoint1, int endPoint1, int startPoint2, int endPoint2, int k) {
        if (endPoint1 == 0) {
            //num1 empty
            return nums2[startPoint2 + k - 1];
        }
        if (endPoint2 == 0) {
            //num2 empty
            return nums1[startPoint1 + k - 1];
        }

        if (k == 1) {
            return Math.min(nums1[startPoint1], nums2[startPoint2]);
        }

        int point1 = (endPoint1 - startPoint1) / 2;
        int point2 = (endPoint2 - startPoint2) / 2;
        if (point1 == 0 && point2 == 0 && k == 2) {
            return Math.max(nums1[0], nums2[0]);
        }
        if (nums1[point1] < nums2[point2]) {
            k = k - point1  - startPoint2;
            return getMinKth(nums1, nums2, point1, endPoint1, startPoint2, endPoint2, k);
        } else {
            k = k - startPoint1 - point2;
            return getMinKth(nums1, nums2, startPoint1, endPoint1, point2, endPoint2, k);
        }

    }

    @Test
    public void test() {
//        Assert.assertEquals(2.0, findMedianSortedArrays(new int[]{1,3}, new int[]{2}), 0.0);
//        Assert.assertEquals(2.5, findMedianSortedArrays(new int[]{1,2}, new int[]{3,4}), 0.0);
//        Assert.assertEquals(1.0, findMedianSortedArrays(new int[]{1}, new int[]{}), 0.0);
//        Assert.assertEquals(-1.0, findMedianSortedArrays(new int[]{3}, new int[]{-2,-1}), 0.0);
        Assert.assertEquals(1.5, findMedianSortedArrays(new int[]{1,2}, new int[]{-1,3}), 0.0);
    }
}